package com.xieyong.leetcode;

import java.util.Arrays;

public class Leetcode3445 {

    long startTime;
    long endTime;

    public static void main(String[] args) {
        Leetcode3445 leetcode3445 = new Leetcode3445();
        String s = "4242104443334031012204313023034100431323421203342223202003431120113103344342004123011231202000141121011401131030114033322200201300032211022312004020330443112230331032101420114110413012340213124103403131243322310333420440423344300042333300020114434322010232031042313004023312234200431331234330233301204003202220123411111412104103120024310404404241320241003100341241312211141043143322444224134443141204431310411144341442400131431203313311241343232244343043201033131331323340414134113301442132010422434202110110303341021403111120400410120441004123102233021441430242400123401103242433230422113124444420043223434443241431011301131403243424413142300043233023403430103130032032441123100223444210040301231403332141020402130110402324331223202313340430120131002243113032433224311024020113204024100304142413304230241412414312301121240423433140000003120444323423042013314424400032032141013422244240422134113100220041321422013203320314214343112342200303331241120422244100220034234303040303041220242002014244230002114433423341130230214044443031200024042412042344434041420223330321143323233422023112130204121321211310133024403010422111320132411302024122302400312010133443323310123130211040210220001410443404214123142000422044414230313002321020244030220210310043014040312330100304433113404022011222020042042210324022330044343131240404043332144024234142411421141031440242130332420131234221304334211031022412100044003002012010134422333340334330013241334333410034231040411000314004300204203314321204341214000020222234230344204214022223041010122440300220411130303133343302111341114122303311123432041230410112021202413223124411042211314204310300400343032031020114432222212224112130330220103040312104044110002031223313102403424023411302201403304000111214100230243200141420421210412404023432100131442012143131323142443204112411211340040113214320030212022224403044144332311023003214044122304104140021442144233422412120121411104430341241331043024312220401331230112143122233420114134233011122022134144312322224402020134042204221341141144131402320220140042314003212340023432300020422334100242224012312413030140143203244420342403432001324303334303120401401332410040313444432010220332321400231243230013230211300131012100310123214313441011241134443423121223110343044113401230033431333333142303030011324032303234212322032331221043302122242211432432234414413302424404121213002214140434212010302402213233413404242322440322411333032042010004200330402341321423232311312242131244333111421004240322404140343022041324002030100122201040002131232122100002324314302102014311302322400043014013410002401441332010040231240101231440032423204132042200320103144040424221304313342230323343322310424120034240440010301144032134014011032013301041210422330141011120031210404323433413102402404220020014402122002220010123221130401140121204232104430232211431211224234443320440443304103333143242003401030413103131010133123231012322224014314133303000210024311420044402021013100401314404011440112330103224004201000403031423321434414404243221234041231141303420400214342434001220001222410123404034040014041041032332241314323334100224334002031231133013241304134211323042023100044231142423302340120244341100132231043211303432440002410220410004210040440202014441242130033100322242241123322231033033011222410034442231002033121043212430401212032432043211321303141200000342404042101312443301301140213100130301140134010424414111422030401312002034230211233134432331333222002320140234301444110122324211421344044414124230431031321400432300110300032103333210221400001222341241010214402301214342434231324240302132443411323444103123232003020441033010232431024420142434212300114014333144444214421320122020142310414222442023232214041023412230222433024040302421344324430402031424002103400433303123044234300041410423221431202410134322044422342020422023031124313023400443211323231132442212320021112234432344343203132134240004413103043014222114043444300324213204130331014212012400211042003210033142204200414143043221314031411000004421002443333441031031304121034221430322221341341244430440304040012012224130340032440010343323042104004100334201114432234020133224332031442242042330040310401430323433012144404013041413331134234223134121302221243233302102034311412213320040403240303332423301212134022411022402004244443141242422333000414213102432441231302111234101312130303402430422104412430203120034121324130134412214134012443424412112422212000123300443443210403322333101224403140211322404001113234220214344243420041312312131203323102032124123410242302302300314043101341114123300122430220441343210042414412434024114322140142210212123220130003442101122310122242230420434444104044401003233220404031120213241410212334423443232013340222143222421041331301313343043014313400334131041002333243330123222223312313042141331444342442211023412003130144142110414242204343123143113004002122400234030441343240431413422234402042414421302434103043302111242042311430233013042004100022300223321330213442033342223303333223330024334433134440424300043431044012411243301433222203234211334424002440402140303104220121433413141244301134333244222223041241114302220312434110201042320022430303121034130134422143000330310404141113100021421232321044042101443211111003230214424434310220434141333123332432314243101440344023323413042323331231032244240433422244122214344111241420323312242014104322220333223343040023301032024142422334342221132410123043041411301310142134303130434411444014043404324230122422101112030210113121313110144143221403201440211041230320033221112331000323021014114243301400144422123141432120134413444432010110111401202232344202120124321403000434104034134301443141104421102303201404124134441304102332442410121432413410213222333434143144340240320432043140404204134040102313040101401012040431124423414442013340313344341010204041201220142412412231304024421333132402141002124001011112222210433141320100132430341234224424324140232021412332223430021322312130000244202423002043132233211120022443022033131222433004014102100320420224011104103243122203431320324042001002202110002124234342113433041103034231022110200432441343142033343414413144012003324041130443013042323121144231223433311012103223232211000440003401001301401444040112304021311312413042102242301203140441444112341221020204214032111111343034312313322422141142020200021420221243131000104401434423133144330322024103403401311404032321144343224031131324124342212403310121343331104113044014333304040000410441121443314430421040124044021421103401210104004341021123232013021304231222431404114124410333031421431012234340330432242322214212142332214413102110323202041320341331342310442302314233001030242013021444000440010100341021232124024043114140340102342124143030222132140124342333202123110130101023442413101033434204444241321312322004100001211123401431224013340412423140131230041123313401114004004413323310304200023132301442412141202334132230312142041320401344012244211222121222123113001220143031103103021103040002323134344014420424343020132143231212211022023311100411343220034400231330241030003212422034010022104400010140100220243310243444304130424140044134303424430124001341042004401222034220233321000133034240432043140021214302143333241214121102324144231001120134043122301310032431011243231214210211332302001323242223412304210141101213213213123440424221041312004310321234044414214401044322413440243442421442032222244320242344320202110343040413233303321443243412022000240031341111314433411111214044410203121201114014010134434210410420102104110323132321332413442424431421000220103323111244340044122030213404123113231241001111233224021420011100003122323024304340023414411414032143322210220423033342024044334322233014034313313321332340122012131421330002034300220100444013411140210123043432404112410111413330312422042440022000131413230440113443323002120410400244002312204033044033002433134441100020411124220303211010442444144400112344443202232020404121323443020233210313020302134443234233412201104432203402201312012221224320332111211134101212324242314133334032402320331341042112143030041431011201433302111341341213344234042443300443444323402044224401203141303034241044423001324223121324142123411232312414404301001303224443403100123102032234303440430141443110034042203324342233441010002042331440110024333141343223312214114404140020024214031004213141014333304342023413240022214001243114230414303332002000200044243221302200112432024014141204441012120400410333142040234122323234120441124111214334403342212430014214210314203112431434033003430011402412122234331430410320321212234134034134233200120011143143304433433432343001134002141344444102244123044013113421041313123422402132131241204421024224021042334302103140131424010221411012004304413430410111";
        int k = 947;
        leetcode3445.startTime = System.currentTimeMillis();
        int i = leetcode3445.maxDifference(s, k);
        leetcode3445.endTime = System.currentTimeMillis();
        System.out.println(i);
        System.out.println("时长：" + (leetcode3445.endTime - leetcode3445.startTime));
    }

//    不会了，题解都是数学运算,  ...效率惊人，平均10ms
    public int maxDifference(String s, int k) {
        int n = s.length();
        int ans = Integer.MIN_VALUE;
        for (char a = '0'; a <= '4'; ++a) {
            for (char b = '0'; b <= '4'; ++b) {
                if (a == b) {
                    continue;
                }
                int[] best = new int[4];
                Arrays.fill(best, Integer.MAX_VALUE);
                int cnt_a = 0, cnt_b = 0;
                int prev_a = 0, prev_b = 0;
                int left = -1;

                for (int right = 0; right < n; ++right) {
                    cnt_a += (s.charAt(right) == a) ? 1 : 0;
                    cnt_b += (s.charAt(right) == b) ? 1 : 0;

                    while (right - left >= k && cnt_b - prev_b >= 2) {
                        int left_status = getStatus(prev_a, prev_b);
                        best[left_status] = Math.min(best[left_status], prev_a - prev_b);
                        ++left;
                        prev_a += (s.charAt(left) == a) ? 1 : 0;
                        prev_b += (s.charAt(left) == b) ? 1 : 0;
                    }

                    int right_status = getStatus(cnt_a, cnt_b);
                    if (best[right_status ^ 0b10] != Integer.MAX_VALUE) {
                        ans = Math.max(ans, cnt_a - cnt_b - best[right_status ^ 0b10]);
                    }
                }
            }
        }
        return ans;
    }

    private int getStatus(int cnt_a, int cnt_b) {
        return ((cnt_a & 1) << 1) | (cnt_b & 1);
    }

//  超时了 平均600ms
//    public int maxDifference(String s, int k) {
//        int[][] prefixSumCount = new int[5][s.length() + 1];
//        for (int i = 0; i < 5; i++) {
//            Arrays.fill(prefixSumCount[i], 0);
//        }
//        char[] chars = s.toCharArray();
//        for (int i = 1; i <= chars.length; i++) {
//            int ch = chars[i - 1] - '0';
//            for (int j = 0; j < 5; j++) {
//                if (ch == j) {
//                    prefixSumCount[j][i] = prefixSumCount[j][i - 1] + 1;
//                } else {
//                    prefixSumCount[j][i] = prefixSumCount[j][i - 1];
//                }
//            }
//        }
//        int res = Integer.MIN_VALUE;
//        for (int i = 0; i < chars.length - k + 1; i++) {
//            for (int j = i + k; j < chars.length + 1; j++) {
//                int maxoddcount = 0;
//                int minevencount = Integer.MAX_VALUE;
//                for (int l = 0; l < 5; l++) {
//                    int count = prefixSumCount[l][j] - prefixSumCount[l][i];
//                    if (count > 0 && count % 2 == 0) {
//                        minevencount = Math.min(minevencount, count);
//                    } else if (count > 0) {
//                        maxoddcount = Math.max(maxoddcount, count);
//                    }
//                }
//                res = Math.max(res, maxoddcount - minevencount);
//            }
//        }
//        return res;
//    }
}
